package puzzle.puzzleup2008;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class FourRegions {

	static int regionSize = 4;
	static List<RegionType> regionTypes = getAllRegionType(regionSize);
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		search();
	}

	private static void search() {
		LinkedList<Region> regions = new LinkedList<Region>();
		Point point = new Point(0, 0);
		Region tmpr = findNextRegionFor(regions, point, 0, -1);
		regions.add(tmpr);
		
		int count = 0;
		while (regions.size() > 0) {

			Point p = null;
			Region region = null;
			p = findPoint(regions);
//			print(regions);
			if (p != null) {
				region = findNextRegionFor(regions, p, 0, -1);
			}
			if (region != null) {
				regions.add(region);
//				print(regions);
			} else {
				if ( p == null) {
					count ++;
					print(regions);
				}
				
				//backtrace
				while (regions.size() > 0) {
					Region r = regions.removeLast();
//					print(regions);
					Region nr = findNextRegionFor(regions, r.point, r.indexOfType, r.indexOfGrid);
					if (nr != null) {
						regions.add(nr);
//						print(regions);
						break;
					} else {
						continue;
					}
				}
			}
		}
		System.out.println(count);
	}
	
	private static void print(List<Region> regions) {
		
		for (int y = 0; y < regionSize; y ++) {
			for (int x = 0; x < regionSize; x ++) {
				Point p = new Point(x, y);
				int index = -1;
				for (int i = 0; i < regions.size(); i ++) {
					if (regions.get(i).getPoints().contains(p)) {
						index = i;
						break;
					}
				}
				if (index == -1) {
					System.out.print("*");
				} else {
					System.out.print(index);
				}
			}
			System.out.println();
		}
		System.out.println("\n\n");
	}
	
	private static Point findPoint(List<Region> regions) {
		
		List<Point> points = getAllPoints(regions);
		for (int y = 0; y < regionSize; y ++) {
			for (int x = 0; x < regionSize; x ++) {
				Point p = new Point(x, y);
				if (!points.contains(p)) {
					return p;
				}
			}
		}
		return null;
	}
	
	private static List<Point> getAllPoints(List<Region> regions) {
		
		List<Point> points = new ArrayList<Point>();
		for (Region region: regions) {
			points.addAll(region.getPoints());
		}
		return points;
	}
	
	private static Region findNextRegionFor(List<Region> regions, 
			Point point, int typeIndex, int gridIndex) {
		
		List<Point> points = getAllPoints(regions);
		int indexOfType = 0;
		int indexOfGrid = 0;
		if (gridIndex < regionSize) {
			indexOfGrid = gridIndex + 1;
			indexOfType = typeIndex;
		} else {
			indexOfGrid = 0;
			indexOfType = typeIndex + 1;
		}
		while (indexOfType < regionTypes.size()) {
			while (indexOfGrid < regionSize) {
				Region r = new Region(point, indexOfType, indexOfGrid);
				List<Point> ps = r.getPoints();
				boolean ok = true;
				for (Point p: ps) {
					if (p.x < 0 || p.y < 0 
						|| p.x >= regionSize || p.y >= regionSize 
						|| points.contains(p)) {
						ok = false;
						break;
					}
				}
				if (ok) {
					return r;
				}
				indexOfGrid ++;
			}
			indexOfGrid = 0;
			indexOfType ++;
		}
		return null;
	}
	
	private static class Region {
		
		Point point;		//
		int indexOfType;	//see regionType
		int indexOfGrid;	//index in the regionType
		
		public Region(Point point, int indexOfType, int indexOfGrid) {
			this.point = point;
			this.indexOfType = indexOfType;
			this.indexOfGrid = indexOfGrid;
		}
		
		public List<Point> getPoints() {

			List<Point> points = new ArrayList<Point>();
			RegionType regionType = regionTypes.get(indexOfType);
			for (int i = 0; i < regionType.size(); i ++) {
				Point newPoint = new Point();
				newPoint.x = point.x + (regionType.get(i).x-regionType.get(indexOfGrid).x);
				newPoint.y = point.y + (regionType.get(i).y-regionType.get(indexOfGrid).y);
				points.add(newPoint);
			}
			return points;
		}
	}
	
	private static class Point {
		int x;
		int y;
		
		public Point() {
			this.x = 0;
			this.y = 0;
		}
		
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Point) {
				Point p = (Point)obj;
				return (this.x == p.x && this.y == p.y);
			} else {
				return false;
			}
		}
		
		public Point move(int dx, int dy) {
			return new Point(x+dx, y+dy);
		}
		
		@Override
		public String toString() {
			return "(" + this.x + ", " + this.y + ")";
		}
		
		
	}
	
	/**
	 * 所谓RegionType，是由一组不同的方格组成的联通区域。
	 * 每个方格都可以通过移动到相邻方格的方式到达其他任何一个方格。
	 * 所谓“相邻”，是指具有公共边。
	 * 这里用Point表示一个方格。
	 * @author wong tong
	 *
	 */
	private static class RegionType extends ArrayList<Point> {

		private static final long serialVersionUID = -8792132652356125566L;
		
		private boolean regular = false;
		
		public RegionType extend(Point point) {
			
			RegionType newRegion = new RegionType();
			for (int i = 0; i < this.size(); i ++) {
				Point p = this.get(i);
				newRegion.add(new Point(p.x, p.y));
			}
			newRegion.add(point);
			return newRegion;
		}
		
		/**
		 *  正规化一个Region
		 *
		 */
		@SuppressWarnings("unchecked")
		public void regular() {
			if (!this.regular) {
				Point[] points = this.toArray(new Point[this.size()]);
				//step 1
				int minx = Integer.MAX_VALUE, miny = Integer.MAX_VALUE;
				for (Point point: points) {
					if (minx > point.x) {
						minx = point.x;
					}
					if (miny > point.y) {
						miny = point.y;
					}
				}
				
				for (Point point: points) {
					point.x -= minx;
					point.y -= miny;
				}

				//sort
				Arrays.sort(points, new Comparator(){

					public int compare(Object obj1, Object obj2) {
						Point p1 = (Point)obj1;
						Point p2 = (Point)obj2;
						if (p1.y < p2.y) {
							return -1;
						} else if (p1.y > p2.y) {
							return +1;
						} else {
							if (p1.x < p2.x) {
								return -1;
							} else if (p1.x > p2.x) {
								return +1;
							}
						}
						return 0;
					}
				});
				//update instance
				this.clear();
				for (Point point: points) {
					this.add(point);
				}
				
				this.regular = true;
			}
		}
		
		@Override
		public boolean equals(Object obj) {
			if (obj instanceof RegionType) {
				RegionType r = (RegionType)obj;
				return r.toString().equalsIgnoreCase(this.toString());
			} else {
				return false;
			}
		}
		
		@Override
		public String toString() {
			this.regular();
			int maxx = -1, maxy = -1;
			for (Point point: this) {
				if (maxx < point.x) {
					maxx = point.x;
				}
				if (maxy < point.y) {
					maxy = point.y;
				}
			}
			
			String str = "\n";
			for (int y = 0; y <= maxy; y ++) {
				for (int x =0; x <= maxx; x ++) {
					if (this.contains(new Point(x, y))) {
						str += "O";
					} else {
						str += " ";
					}
				}
				str += "\n";
			}
			return str;
		}
	}
	
	/**
	 * 获得所有可能的，由n个方格组成的区域。
	 * 不考虑旋转等。
	 * @param n
	 * @return
	 */
	public static List<RegionType> getAllRegionType(int n) {
		
		if (n <= 0) {
			throw new RuntimeException();
		} else {
			LinkedList<RegionType> regions = new LinkedList<RegionType>();
			//first region
			Point point = new Point(0, 0);
			List<Point> points= new ArrayList<Point>();
			points.add(point);
			RegionType region = new RegionType();
			region.addAll(points);
			regions.add(region);
			
			int size = 1;
			while (size < n) {
				while (regions.peek().size() == size) {
					RegionType r = regions.removeFirst();
					List<RegionType> exrs = extend(r);
					for (RegionType tmpr: exrs) {
						if (!regions.contains(tmpr)) {
							regions.add(tmpr);
						}
					}
				}
				size ++;
			}
			
			return regions;
		}
	}
	
	/**
	 * 增加一个方格，来扩展当前的Region
	 * @param region
	 * @return
	 */
	public static List<RegionType> extend(RegionType region) {
		
		List<RegionType> rs = new ArrayList<RegionType>();
		for (Point point: region) {
			rs.addAll(extendAt(region, point));
		}
		return rs;
	}
	
	/**
	 * 增加一个与Point相邻的方格来扩展Region
	 */
	public static List<RegionType> extendAt(RegionType region, Point point) {
		
		List<RegionType> rs = new ArrayList<RegionType>();
		Point[] newPoints = new Point[] {
				point.move(0,+1),
				point.move(0,-1),
				point.move(-1,0),
				point.move(+1,0)
		};
		
		for (Point newPoint: newPoints) {
			if (!region.contains(newPoint)) {
				rs.add(region.extend(newPoint));
			}
		}
		return rs;
	}
}